#
# @lc app=leetcode.cn id=42 lang=python3
#
# [42] 接雨水
#
# @lc code=start
# class Solution:
#     def trap(self, height: List[int]) -> int:
#         if not height:
#             return 0
#         n = len(height)
#         # 1.动态规划
#         # dp数组有2个,left_max和right_max,能分别传递左边,右边最高的柱子.
#         left_max = [height[0]]+[0]*(n-1)
#         for i in range(1,n): # [1,n-1]
#             left_max[i] = max(left_max[i-1], height[i])    

#         right_max = [0]*(n-1)+[height[n-1]]
#         for i in range(n-2, -1, -1): # 注意:范围[n-2,0],顺序
#             right_max[i] = max(right_max[i+1], height[i])

#         # print(height)
#         # print(left_max)
#         # print(right_max)
#         res = 0
#         for i in range(n):
#             h = min(left_max[i], right_max[i])-height[i]
#             # h = 0 if h<0 else h
#             res += h
#             print(f'{left_max[i]}<-{height[i]}->{right_max[i]} h{h}')
#         return res
class Solution:
    def trap(self, height: List[int]) -> int:
        if not height:
            return 0
        n = len(height)
        # 2.单调栈
        # 要想接雨水,找右边第一个比它大的柱子,
        # (左边第一个比它小的柱子就在单调栈里,它的旁边)
        s = [0] # 把第一个元素的下标入栈初始化
        res = 0 # 面积
        for i in range(1, n): # [1,n-1]  
            if height[i] <= height[s[-1]]: # 栈顶
                s.append(i)
                print(s)
            else:
                while s and height[i]>height[s[-1]]:
                    idx = s.pop() 
                    mid = height[idx]
                    if s: # 之前出栈,这里需要判断是否为空
                        h = min(height[s[-1]], height[i])-mid
                        w = i-s[-1]-1   
                        res += h*w
                    print(s)
                s.append(i)
                
        return res
        
# @lc code=end

